{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Complement of Base 10 Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bitwiseComplement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #十进制整数的反码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>每个非负整数&nbsp;<code>N</code>&nbsp;都有其二进制表示。例如，&nbsp;<code>5</code>&nbsp;可以被表示为二进制&nbsp;<code>&quot;101&quot;</code>，<code>11</code> 可以用二进制&nbsp;<code>&quot;1011&quot;</code>&nbsp;表示，依此类推。注意，除&nbsp;<code>N = 0</code>&nbsp;外，任何二进制表示中都不含前导零。</p>\n",
    "\n",
    "<p>二进制的反码表示是将每个&nbsp;<code>1</code>&nbsp;改为&nbsp;<code>0</code>&nbsp;且每个&nbsp;<code>0</code>&nbsp;变为&nbsp;<code>1</code>。例如，二进制数&nbsp;<code>&quot;101&quot;</code>&nbsp;的二进制反码为&nbsp;<code>&quot;010&quot;</code>。</p>\n",
    "\n",
    "<p>给你一个十进制数&nbsp;<code>N</code>，请你返回其二进制表示的反码所对应的十进制整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>5 的二进制表示为 &quot;101&quot;，其二进制反码为 &quot;010&quot;，也就是十进制中的 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>7\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>7 的二进制表示为 &quot;111&quot;，其二进制反码为 &quot;000&quot;，也就是十进制中的 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>10\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>10 的二进制表示为 &quot;1010&quot;，其二进制反码为 &quot;0101&quot;，也就是十进制中的 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>0 &lt;= N &lt; 10^9</code></li>\n",
    "\t<li>本题与 476：<a href=\"https://leetcode-cn.com/problems/number-complement/\">https://leetcode-cn.com/problems/number-complement/</a> 相同</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [complement-of-base-10-integer](https://leetcode.cn/problems/complement-of-base-10-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [complement-of-base-10-integer](https://leetcode.cn/problems/complement-of-base-10-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '7', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        copy = n\n",
    "        mask = 1\n",
    "        while copy > 0:\n",
    "            mask <<= 1\n",
    "            copy >>= 1\n",
    "        mask = max(mask - 1, 1)\n",
    "        return n ^ mask\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        N = bin(n)[2:]\n",
    "        N = N.replace('0','2')\n",
    "        N= N.replace('1','0')\n",
    "        N = N.replace('2','1')\n",
    "        return int(N,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n=5\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        self.n=n\n",
    "        wig=len(bin(self.n)[2:])\n",
    "        return self.n^int('0b'+'1'*wig,2)\n",
    "        \n",
    "\n",
    "if __name__ == '__main__':\n",
    "    S=Solution()\n",
    "    S.bitwiseComplement(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s=bin(n)\n",
    "        p=1\n",
    "        ans=0\n",
    "        for i in range(len(s)-1,1,-1):\n",
    "            if s[i]==\"0\":\n",
    "                ans+=p\n",
    "            # print(i,p,s[i],ans)\n",
    "            p*=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s=f\"{n:b}\"\n",
    "        ans=\"\"\n",
    "        for i in s:\n",
    "            if i==\"1\":\n",
    "                ans+=\"0\"\n",
    "            else:\n",
    "                ans+=\"1\"\n",
    "        return int(ans,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        res = []\n",
    "        for c in bin(n)[2:]:\n",
    "            if c == '0':\n",
    "                res.append('1')\n",
    "            else:\n",
    "                res.append('0')\n",
    "        return int(''.join(res), 2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        return int(str(bin(n)[2:]).replace(\"0\",\"2\").replace(\"1\",\"0\").replace(\"2\",\"1\"),2)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if n >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return n ^ mask\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        b=bin(n)[2:]\n",
    "        t=''.join('1' if char=='0' else '0' for char in b)\n",
    "        i=int(t,2)\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        ans=0\n",
    "        s=str(bin(n))[2:][::-1]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==\"0\":\n",
    "                ans+=2**i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, N: int) -> int:\n",
    "        Nbin=bin(N)\n",
    "        return 2**len(Nbin[2:])-1-N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        ans = 1\n",
    "        while True:\n",
    "            if n >= ans:\n",
    "                ans <<= 1\n",
    "            else:\n",
    "                return ans - n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "      if 0 == n:\n",
    "        return 1\n",
    "      t = 0\n",
    "      while 2 ** t <= n:\n",
    "        t += 1\n",
    "      # print(f\"n{n} t{t} \")\n",
    "      return n ^ (2 ** t - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        mask = 1 << n.bit_length()\n",
    "        return n ^ mask - 1 if mask > 1 else 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, N: int) -> int:\n",
    "        N = bin(N)[2:]\n",
    "        N = N.replace(\"0\",\"2\")\n",
    "        N = N.replace(\"1\",\"0\")\n",
    "        N = N.replace('2','1')\n",
    "        return int(N,2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        result, i = 0, 0\n",
    "        while n != 0:\n",
    "            if n % 2 == 0:\n",
    "                result += pow(2, i)\n",
    "            n //= 2\n",
    "            i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        ans=str(bin(n))[2:].replace('1','0').replace('0','1')\n",
    "        return int(ans,2)^n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 31):\n",
    "            if n >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return n ^ mask  # 异或"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        bin_len = max(1, n.bit_length())\n",
    "        return ((1 << bin_len) - 1) ^ n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if n >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return n ^ mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        copy = n\n",
    "        mask = 2\n",
    "        while copy > 1:\n",
    "            mask <<= 1\n",
    "            copy >>= 1\n",
    "        return n ^ mask - 1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        copy = n\n",
    "        highest_one = 0\n",
    "        while copy > 0:\n",
    "            copy >>= 1\n",
    "            highest_one += 1\n",
    "        if highest_one == 0:\n",
    "            return 1\n",
    "        mask = (1 << highest_one) - 1\n",
    "        return n ^ mask\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        copy = n\n",
    "        mask = 2\n",
    "        while copy > 1:\n",
    "            mask <<= 1\n",
    "            copy >>= 1\n",
    "        return n ^ mask - 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        return 2**(len(bin(n))-2) - n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "\n",
    "        bn = bin(n)[2:]\n",
    "        bn = bn.replace('1', '2')\n",
    "        bn = bn.replace('0', '1')\n",
    "        bn = bn.replace('2', '0')\n",
    "\n",
    "        return int(bn, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        bin_n=bin(n)[2:]\n",
    "        print(bin_n)\n",
    "        all_1= \"\".join([\"1\" for i in range(len(bin_n))])#生成满满的1\n",
    "        print(all_1)\n",
    "        num_10=int(all_1,2)\n",
    "        print(num_10)\n",
    "        return n^num_10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        x = bin(n)\n",
    "        lenth = len(x) - 2\n",
    "        a = ''.join([\"1\" for i in range(lenth)])\n",
    "        b = int(a,2)\n",
    "        return n^b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        nbin=bin(n)\n",
    "        return 2**len(nbin[2:])-1-n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        a=list('{:b}'.format(n))\n",
    "        for i in range(len(a)):\n",
    "            if a[i]=='1':\n",
    "                a[i]='0'\n",
    "            elif a[i]=='0':\n",
    "                a[i]='1'\n",
    "        b='0b'+''.join(a)\n",
    "        #print(b)\n",
    "        return int(b,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        ans = ''\n",
    "        for i in bin(n)[2:]:\n",
    "            ans += '0' if i == '1' else '1'\n",
    "        return int(ans,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        copy = n\n",
    "        mask = 2\n",
    "        while copy > 1:\n",
    "            mask <<= 1\n",
    "            copy >>= 1\n",
    "        return n ^ mask - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        num=n\n",
    "        cnt=0\n",
    "        while num //2>0:\n",
    "            num//=2\n",
    "            cnt+=1\n",
    "        return n^(2**(cnt+1)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "            \n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while n:\n",
    "            if not n & 1:\n",
    "                cnt |= 1 << i\n",
    "            i += 1\n",
    "            n >>= 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "      if 0 == n:\n",
    "        return 1\n",
    "      t = 0\n",
    "      while 2 ** t <= n:\n",
    "        t += 1\n",
    "      # print(f\"n{n} t{t} \")\n",
    "      return n ^ (2 ** t - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        rs=0\n",
    "        fa=1\n",
    "        if n==0:\n",
    "            return 1\n",
    "        while(n!=1):\n",
    "            \n",
    "            t=(1-n%2)\n",
    "            rs+=fa*t\n",
    "            n//=2\n",
    "            fa*=2\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        res = ''\n",
    "        bin_num = bin(n)[2:]\n",
    "        for num_ch in bin_num:\n",
    "            if num_ch == '1':\n",
    "                res += '0'\n",
    "            else:\n",
    "                res += '1'\n",
    "        return int(res, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        N = bin(n)[2:]\n",
    "        N = N.replace('0','2')\n",
    "        N= N.replace('1','0')\n",
    "        N = N.replace('2','1')\n",
    "        return int(N,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        copy = n\n",
    "        mask = 2\n",
    "        while copy > 1:\n",
    "            mask <<= 1\n",
    "            copy >>= 1\n",
    "        return n ^ mask - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        x = bin(n)\n",
    "        length = len(x) - 2\n",
    "        a = \"\".join([\"1\" for i in range(length)])\n",
    "        b = int(a,2)\n",
    "        return n^b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        rs = 0\n",
    "        num = 1\n",
    "        while n > 0:\n",
    "            x = n % 2\n",
    "            if x == 0:\n",
    "                rs += num\n",
    "            num *= 2\n",
    "            n = n >> 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        n_list = []\n",
    "        while n >= 1:\n",
    "            n_list.insert(0, n%2)\n",
    "            n //= 2\n",
    "        new_list = [1-i for i in n_list]\n",
    "        sums = 0\n",
    "        for k, v in enumerate(new_list):\n",
    "            sums += v * 2**(len(new_list)-1-k)\n",
    "        return sums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        return pow(2,int(log(n,2))+1)-1-n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        binary = bin(n)[2:]\n",
    "        print(\"binary is\", binary)\n",
    "        binaryStr = str(binary)\n",
    "        inverseStr = ''.join(['1' if i == '0' else '0' for i in binaryStr])\n",
    "\n",
    "        return int(inverseStr, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        lenn = bin(n)\n",
    "        return 2**len(lenn[2:]) - 1 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        bins = []\n",
    "        while n:\n",
    "            bit = n & 1\n",
    "            bins.append('0' if bit else '1')\n",
    "            n >>= 1\n",
    "        return int(\"\".join(reversed(bins)), base=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        return pow(2,int(log(n,2))+1)-1-n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def bitwiseComplement(self, n: int) -> int:\n",
    "    #     # 跟反码做 | 运算一定是全1,即找到该范围内的最大值即可\n",
    "    #     if n <= 1:\n",
    "    #         return 1 - n\n",
    "    #     cnt = 2\n",
    "    #     while cnt <= n:\n",
    "    #         cnt *= 2\n",
    "    #     return cnt -1 - n\n",
    "    \n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        # 找到最左侧的1\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if n >= (1 << i):   # 1 << i 一次向右移动pow(2,i)\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        # print(n, mask)\n",
    "        return n ^ mask   # n^m=mask  => n^m^n=m=mask^n\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        bin_n = bin(n)[2:]\n",
    "        con_bin_n=''\n",
    "        for i in bin_n:\n",
    "            con_bin_n += str(1-int(i))\n",
    "        sum = 0\n",
    "        length = len(con_bin_n)\n",
    "        for i in range(length):\n",
    "            sum = sum + (int(con_bin_n[i])*2**(length-i-1))\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        for i in range(int(math.log2(n))+1):\n",
    "            n ^= (1 << i)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        ans = ''\n",
    "        for i in bin(n)[2:]:\n",
    "            ans += '0' if i == '1' else '1'\n",
    "        return int(ans,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s = str(bin(n))[2:]\n",
    "        new_s = \"\"\n",
    "        for i in s:\n",
    "            if i == \"1\":\n",
    "                new_s += \"0\"\n",
    "\n",
    "            else:\n",
    "                new_s += \"1\"\n",
    "        return int(new_s, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        mask = max(1 << n.bit_length(), 2)\n",
    "        return n ^ mask - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "\n",
    "        bn = bin(n)[2:]\n",
    "        bn = bn.replace('1', '2')\n",
    "        bn = bn.replace('0', '1')\n",
    "        bn = bn.replace('2', '0')\n",
    "\n",
    "        print(bn)\n",
    "        return int(bn, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "      if 0 == n:\n",
    "        return 1\n",
    "      t = 0\n",
    "      while 2 ** t <= n:\n",
    "        t += 1\n",
    "      print(f\"n{n} t{t} \")\n",
    "      return n ^ (2 ** t - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        num = n\n",
    "        cnt = 0\n",
    "        while num // 2 > 0:\n",
    "            num //= 2\n",
    "            cnt += 1\n",
    "        return n ^ (2**(cnt+1)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s = bin(n)[2:]\n",
    "        t = ''\n",
    "        for i in s:\n",
    "            if i=='0':\n",
    "                t += '1'\n",
    "            else:\n",
    "                t +='0'\n",
    "        return int(t,base=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        for i in range(30,-1,-1):\n",
    "            if((1<<i)&n):\n",
    "                return ((1<<(i+1))-1)^n \n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        highbit = 0\n",
    "\n",
    "        for i in range(1,30+1):\n",
    "            if n >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit+1)) - 1\n",
    "        return n ^ mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        # 跟反码做 | 运算一定是全1,即找到该范围内的最大值即可\n",
    "        if n <= 1:\n",
    "            return 1 - n\n",
    "        cnt = 2\n",
    "        while cnt <= n:\n",
    "            cnt *= 2\n",
    "        return cnt -1 - n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if n >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return n ^ mask\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        for i in range(n.bit_length()):\n",
    "            n ^= 1 << i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        num=n\n",
    "        cnt=0\n",
    "        while num //2>0:\n",
    "            num//=2\n",
    "            cnt+=1\n",
    "        return n^(2**(cnt+1)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        return 1 if n == 0 else 2 ** (int(math.log2(n)) + 1) - 1 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "            \n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while n:\n",
    "            if not n & 1:\n",
    "                cnt |= 1 << i\n",
    "            i += 1\n",
    "            n >>= 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        nn = bin(n)[2:]\n",
    "        mask = ''.join(['1' for _ in range(len(nn))])\n",
    "        mask = int(mask,2)\n",
    "        return n^mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s = \"\"\n",
    "        for i in bin(n).split(\"b\")[-1]:\n",
    "            if i == \"1\":\n",
    "                s += \"0\"\n",
    "            else:\n",
    "                s += \"1\"\n",
    "        return int(s,2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        n=bin(n)[2:]\n",
    "        n=list(n)\n",
    "        for i in range(len(n)):\n",
    "            if n[i]=='0':\n",
    "                n[i]='1'\n",
    "            else:\n",
    "                n[i]='0'\n",
    "        return int(''.join(n),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        count = 0\n",
    "        res = 0\n",
    "        while n != 0:\n",
    "            if n % 2 == 1:\n",
    "                count += 1\n",
    "                n = n // 2\n",
    "            elif n % 2 == 0:\n",
    "                res += 2 ** count\n",
    "                count += 1\n",
    "                n = n // 2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n==0:return 1\n",
    "        msk=1\n",
    "        m=n\n",
    "        while m:\n",
    "            m>>=1\n",
    "            msk<<=1\n",
    "        return int(n^(msk-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        index = -1\n",
    "        temps = []\n",
    "        for i in range(32):#低位开始\n",
    "            temp = n & (1 << i)#n & (1 << i)，如果当前二进制为1，该表达式为1，否则为0\n",
    "            if temp > 0:\n",
    "                temps.append(1)\n",
    "                index = i #记录最高位\n",
    "            else:\n",
    "                temps.append(0)\n",
    "        ans = 0\n",
    "        if index >= 0:#说明存在1\n",
    "            for i in range(index + 1):\n",
    "                ans += (1 - temps[i]) * (2**i)\n",
    "            return ans\n",
    "        else:#不存在1，即全为0，0的反码为全1\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def bitwiseComplement(self, n: int) -> int:\n",
    "#         if n==0:return 1\n",
    "#         msk=1\n",
    "#         m=n\n",
    "#         while m:\n",
    "#             m>>=1\n",
    "#             msk<<=1\n",
    "#         return int(n^(msk-1))\n",
    "\n",
    "###官解：找最高位\n",
    "class Solution:\n",
    "    def bitwiseComplement(self,n):\n",
    "        hbit=0 ###最高位初始化为0\n",
    "        for i in range(1,31):\n",
    "            if n>=(1<<i):\n",
    "                hbit=i \n",
    "            else:\n",
    "                break\n",
    "        msk=(1<<(hbit+1))-1\n",
    "        return n^msk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        # upper = 36\n",
    "        # lower = 0\n",
    "        # m = (upper + lower) // 2\n",
    "        # while m <= upper and m >= lower:\n",
    "        #     if 2 ** m\n",
    "        return 1 if n == 0 else 2 ** (int(math.log2(n)) + 1) - 1 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        x = bin(n)\n",
    "        lenth = len(x) -2 #二进制字符串有个“0b”会占用两个字符\n",
    "        a = \"\".join([\"1\" for i in range(lenth)])#生成满满的1\n",
    "        b = int(a,2)#转换回十进制运算\n",
    "        return n^b\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        temp = list()\n",
    "        while n:\n",
    "            q,r = divmod(n, 2)\n",
    "            temp.append(r)\n",
    "            n = q\n",
    "        temp.reverse()\n",
    "        ans = [1-val for val in temp]\n",
    "        res = 0\n",
    "        for x in ans:\n",
    "            res = res*2 + x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        N = bin(n)[2:]\n",
    "        N = N.replace('0','2')\n",
    "        N= N.replace('1','0')\n",
    "        N = N.replace('2','1')\n",
    "        return int(N,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "\n",
    "        i = 0\n",
    "        val = 0 \n",
    "        if n==0:\n",
    "            return 1\n",
    "        while n>0:\n",
    "            if n&1==0:\n",
    "                val += 1<<i\n",
    "            i += 1\n",
    "            n >>=1 \n",
    "        \n",
    "        return val \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        return int(''.join('1' if c == '0' else '0' for c in '{:b}'.format(n)), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s=bin(n)[2:]\n",
    "        c=''\n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                c+='0'\n",
    "            else:\n",
    "                c+='1'\n",
    "        return int(c,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s = str(bin(n))[2:]\n",
    "        # print(s)\n",
    "        changeMap = {'1':'0', '0':'1'}\n",
    "        ans = ''.join([changeMap[x] for x in s]).lstrip('0')\n",
    "        # print(f\"ans:{ans}\")\n",
    "        return int(ans, 2) if ans else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bitwiseComplement(self, n: int) -> int:\n",
    "        s = str(bin(n))[2:]\n",
    "        res = ''\n",
    "        for c in s:\n",
    "            res += '0' if c == '1' else '1'\n",
    "        return int(res, 2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
